/*
汉诺塔问题
连接：https://leetcode.cn/problems/hanota-lcci/submissions/
题目：力扣-面试题 08.06. 汉诺塔问题
简介：在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。


解法：
    1. 对于规模为 n 的问题，我们需要将 A 柱上的 n 个盘⼦移动到C柱上。
    2. 规模为 n 的问题可以被拆分为规模为 n-1 的⼦问题：
        a. 将 A 柱上的上⾯ n-1 个盘⼦移动到B柱上。
        b. 将 A 柱上的最⼤盘⼦移动到 C 柱上，然后将 B 柱上的 n-1 个盘⼦移动到C柱上。
    3. 当问题的规模变为 n=1 时，即只有⼀个盘⼦时，我们可以直接将其从 A 柱移动到 C 柱。
    • 需要注意的是，步骤 2.b 考虑的是总体问题中的 ⼦问题b 情况。在处理⼦问题的 ⼦问题b 时，我们
    应该将 A 柱中的最上⾯的盘⼦移动到 C 柱，然后再将 B 柱上的盘⼦移动到 C 柱。在处理总体问题
    的 ⼦问题b 时，A 柱中的最⼤盘⼦仍然是最上⾯的盘⼦，因此这种做法是通⽤的。

    递归函数流程：
    1. 当前问题规模为 n=1 时，直接将 A 中的最上⾯盘⼦挪到 C 中并返回；
    2. 递归将 A 中最上⾯的 n-1 个盘⼦挪到 B 中；
    3. 将 A 中最上⾯的⼀个盘⼦挪到 C 中；
    4. 将 B 中上⾯ n-1 个盘⼦挪到 C 中。
*/

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        dfs(A,B,C,n);
    }
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n)
    {
        if(n==1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        dfs(A,C,B,n-1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B,A,C,n-1);
    }
};